백준 2342번
오늘 풀어본 문제는 백준의 2342번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
승환이는 요즘 “Dance Dance Revolution”이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.
DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 $0$, 위를 $1$, 왼쪽을 $2$, 아래를 $3$, 오른쪽을 $4$ 라고 정하자.
처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.
이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 $1$ 의 위치에 있고, 다른 한 발이 $3$ 의 위치에 있을 때, $3$ 을 연속으로 눌러야 한다면, $3$ 의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.
오랫동안 DDR을 해 온 백승환은 발이 움직이는 위치에 따라서 드는 힘이 다르다는 것을 알게 되었다. 만약, 중앙에 있던 발이 다른 지점으로 움직일 때, $2$ 의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 $3$ 의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 $4$ 의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 $1$ 의 힘을 사용하게 된다.
만약 $1 \to 2 \to 2 \to 4$ 를 눌러야 한다고 가정해 보자. 당신의 두 발은 처음에 (point $0$, point $0$)에 위치하여 있을 것이다. 그리고 $(0, 0) \to (0, 1) \to (2, 1) \to (2, 1) \to (2, 4)$ 로 이동하면, 당신은 $8$ 의 힘을 사용하게 된다. 다른 방법으로 발을 움직이려고 해도, 당신은 $8$ 의 힘보다 더 적게 힘을 사용해서 $1 \to 2 \to 2 \to 4$ 를 누를 수는 없을 것이다.
입력
입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 $1$, $2$, $3$, $4$ 의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 $0$ 은 수열의 마지막을 의미한다. 즉, 입력 파일의 마지막에는 $0$ 이 입력된다. 입력되는 수열의 길이는 $100,000$ 을 넘지 않는다.
출력
한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 힘을 출력한다.
풀이과정
1번째 시도
문제를 보고 DP 문제라는 것을 알 수 있었다. 3차원 배열을 이용하여 이를 해결하기로 했고, 첫 번째 인덱스는 현재 스텝, 두 번째 인덱스는 왼쪽 발의 위치, 세 번째 발의 인덱스는 오른쪽 발의 위치로 설정하였다.
각 인덱스에 저장된 값은 해당 상태에 도달하기까지 필요한 힘의 최소값이며, 만약 해당 상태에 도달하는 것이 불가능하다면 INT_MAX 를 저장하도록 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int getPower(int start, int end);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<int> ddr;
while (true) {
int temp;
cin >> temp;
if (temp == 0) {
break;
}
else {
ddr.emplace_back(temp);
}
}
if (ddr.empty()) {
cout << 0;
return 0;
}
vector<vector<vector<int>>> dp(ddr.size(), vector<vector<int>>(5, vector<int>(5, INT_MAX)));
dp[0][ddr[0]][0] = getPower(0, ddr[0]);
dp[0][0][ddr[0]] = getPower(0, ddr[0]);
for (int step=1; step<ddr.size(); step++) {
for (int right=0; right<5; right++) {
if (ddr[step] == right) {
continue;
}
for (int prevLeft=0; prevLeft<5; prevLeft++) {
int prev = dp[step-1][prevLeft][right];
int curr = prev + getPower(prevLeft, ddr[step]);
if (prev != INT_MAX && dp[step][ddr[step]][right] > curr) {
dp[step][ddr[step]][right] = curr;
}
}
}
for (int left=0; left<5; left++) {
if (ddr[step] == left) {
continue;
}
for (int prevRight=0; prevRight<5; prevRight++) {
int prev = dp[step-1][left][prevRight];
int curr = prev + getPower(prevRight, ddr[step]);
if (prev != INT_MAX && dp[step][left][ddr[step]] > curr) {
dp[step][left][ddr[step]] = curr;
}
}
}
}
int result = INT_MAX;
for (int left=0; left<5; left++) {
for (int right=0; right < 5; right++) {
result = min(result, dp[ddr.size() - 1][left][right]);
}
}
cout << result;
return 0;
}
int getPower(int start, int end) {
if (start == end) {
return 1;
}
else if (start == 0) {
return 2;
}
else if (abs(start - end) == 2) {
return 4;
}
else {
return 3;
}
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
또 DP 문제가 나오고 말았다! DP 문제는 언제나 아이디어 싸움인 것 같다. 그리고 그런 아이디어가 번쩍번쩍 잘 떠오르면 좋을텐데, 아직 그정도의 실력이 되는 것 같지는 않다. 그리고 아이디어가 떠올랐다고 해도, 그걸 구현하는건 다른 이야기인 것 같다.
이제 군대가기까지는 $9$ 일이, CLASS 5 는 $6$ 문제가 남은 상황이다. 이 페이스를 잘 유지한다면 군입대 전에 CLASS 5 는 모두 해치우고 갈 수 있을 것 같다. 마저 힘내서 풀어봐야 겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2342